package com.crl.map.utils.astar
{
	public class OpenList
	{
		private var list:Vector.<Node>;
		private var xyset:XYSet;
		public function OpenList(w:int,h:int)
		{
			list=new Vector.<Node>();
			xyset=new XYSet(w,h);
		}
		
		public function add(node:Node):void{
			xyset.add(node.x,node.y);
			
			var index:int=binarySearchIndex(node.f);
			list.splice(index,0,node);
		}
		
		public function reset(node:Node):void{
			var index:int=getIndex(node);
			list.splice(index,1);
			
			add(node);
		}
		
		private function getIndex(node:Node):int{
			var index:int=binarySearchIndex(node.f);
			
			var len:int=list.length;
			
			for (var i:int=0;i<len;i++){
				if(list[index+i]==node){
					return index+i;
				}
				if(list[index-i]==node){
					return index-1;
				}
			}
			
			return -1;
		}
		
		private function binarySearchIndex(f:int):int{
			var left:int=0;
			var right:int=list.length-1;
			
			var mid:int;
			var midV:Number;
			
			if(right<0){
				return 0
			}
			
			if(left==right){
				if(f>list[0].f){
					return 0;
				}else{
					return 1;
				}
			}
			
			
			while(left<right-1){
				mid=left+(right-left)/2;
				midV=list[mid].f;
				
				if(f<midV){
					left=mid;
				}else if(f>midV){
					right=mid;
				}else{
					return mid;
				}
			}
			
			
			if(left==right-1){
				if(f<list[right].f){
					return right+1;
				}else if(f>=list[left].f){
					return right;
				}else{
					return left;
				}
			}else{
				return left;
			}
			
		}
		
		public function clear():void{
			list.splice(0,list.length);
		}
		
		public function pop():Node{
			if(list.length){
				var node:Node=list.pop();
				xyset.remove(node.x,node.y);
				return node;
			}
			return null;
		}
		
		
		public function contains(node:Node):Boolean{
			return xyset.contains(node.x,node.y);
		}
	}
}